/*
 * Diseno de Algoritmos 2
 * Abril Julio 2011
 * David Subero
 * Daniel Bruzual
 * Job Shop resuelto a traves de GRASP
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <unistd.h>
#include <sys/time.h>
#include <time.h>
#include "Lista.h"

#define MAX(a, b) ((a > b)? a: b)

typedef struct operacion {
	int id;
	int costo;
	int r; //tam del camino mas largo hasta ella desde el inicio
	int t; //tam del camino mas largo desde ella hasta el fin
	int maquina; //maquina a la que pertenece la operacion
	struct operacion *pj;
	struct operacion *sj;
	struct operacion *pm;
	struct operacion *sm;
} operacion;

//numero de trabajos
int nro_t;

//numero de maquinas
int nro_m; 

//numero de operaciones totales 
int nro_op;

/* arreglo que contiene todas las operaciones
 * ordenadas por trabajo, y por precedencia
 * dentro de ese trabajo.
*/
operacion *operaciones;

/* Mejor solucion encontrada hasta el momento representada como una
 * matriz que contiene por cada maquina, las operaciones en el 
 * orden que se realizan en ella
 */
operacion ***mejor_solucion;

//Costo de la mejor solucion hasta el momento
int costo_mejor;

//operaciones iniciales de cada maquina
operacion **inicio; 

//operaciones finales de cada maquina
operacion **fin;

//numero de veces que grasp construye soluciones
int nro_iteraciones;

//restringe la lista de candidatos a escoger
double alfa;

/* Lee el archivo de una instancia e inicializa todas las estructuras
 * Parametros:
 *		archivo: nombre del archivo de la instancia
 * Valor de retorno:
 *		1 si el archivo no existe o si el formato del archivo no es valido
 *		-1 si no hay suficiente memoria disponible
 *		0 en otro caso
 */
int leer_instancia (char *archivo) {
  int i, j, maquina, costo;
  operacion *predecesor;
  FILE *fp;
  if ((fp = fopen(archivo, "r")) == NULL) {
    printf("ERROR: no se encontro el archivo \"%s\"\n",archivo);
    return 1;
  }

  if(!fscanf(fp, "%d %d\n", &nro_t, &nro_m)) {
    printf("ERROR: formato invalido\n");
    return 1;
  }
	
  //todas los trabajos tienen una operacion por maquina
  nro_op = nro_t * nro_m;

  operaciones = (operacion *) calloc(nro_op,sizeof(operacion));
  if (operaciones == NULL) return -1;
  
  mejor_solucion = (operacion ***) calloc(nro_m,sizeof(operacion **));
  if (mejor_solucion == NULL) return -1;
  
  inicio = (operacion **) calloc(nro_m,sizeof(operacion *));
  if (inicio == NULL) return -1;
  
  fin = (operacion **) calloc(nro_m,sizeof(operacion *));
  if (fin == NULL) return -1;
  
  for (i=0; i<nro_m; i++) {
    mejor_solucion[i] = (operacion **) calloc(nro_t,sizeof(operacion *));
    if (mejor_solucion[i] == NULL) return -1;
  }

	
  for (i=0; i<nro_t; i++) {
    predecesor = NULL;
    for (j=0; j<nro_m; j++) {
      if(!fscanf(fp, "%d %d\n", &maquina, &costo)) {
	printf("ERROR: formato invalido\n");
	return 1;
      }
      operaciones[i*nro_m + j].id = i*nro_m + j;
      operaciones[i*nro_m + j].costo = costo;
      operaciones[i*nro_m + j].maquina = maquina;
      operaciones[i*nro_m + j].pj = predecesor;
      operaciones[i*nro_m + j].pm = operaciones[i*nro_m + j].sm = NULL;
      if (j < nro_m - 1) {
	operaciones[i*nro_m + j].sj = operaciones + i*nro_m + j + 1;
      } else {
	operaciones[i*nro_m + j].sj = NULL;
      }
      
      predecesor = operaciones + i*nro_m + j;
    }
  }
  fclose(fp);
  return 0;
}

void imprimir_solucion () {
  int i, j;
  operacion *op;
  printf("Operaciones ordenadas en cada maquina segun se realizan.\n");
  printf("Solucion:\t(job, operation)\n");

  for (i=0; i<nro_m; i++) {
    printf("Maquina %d: ", i);
    op = inicio[i];
    for (j=0; j<nro_t; j++) {
        printf("(%d,%d)  ",op->id / nro_m, op->id % nro_m);
        op = op->sm;
    }
    printf("\n");
  }
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/* Calcula los nodos que estan en el camino critico y
 * guarda el id de cada uno en un arreglo llamado nodos
 * Parametros:
 *		nodos: arreglo que contiene los id de las operaciones que se encuentran
 *			   en el camino critico
 *		primeros: arreglo de operaciones iniciales de cada maquina
 *		costo_sol: entero que representa el costo de la solucion
 *		r_sol: arreglo de tiempos de comienzo mas temprano de cada operacion
 *		t_sol: arreglo de tiempos desde que termina cada operacion hasta que
 *			   finalizan todos los trabajos
 * Valor de retorno:
 *		cantidad de operaciones del camino critico
 */
int camino_critico(int ** nodos, operacion *** solucion, int *posiciones, int costo_sol, int r_sol[], int t_sol[]){
  int i, id, tama;
  operacion* op,* sm,* sj, *sig;
  Lista camino;
  inicializa(&camino);
  
  //buscar la primera operacion de alguna maquina
  //que sea parte de un camino critico
  for(i=0; i<nro_m; i++){
    op = solucion[i][0];
    if(op->costo + t_sol[op->id] == costo_sol){
      //es el primer nodo de un camino critico
      push(op->id, &camino);
      sig = op;
      break;
    }
  }

 //recorrer el grafo buscando UN camino critico
 while(1){
   if (posiciones[sig->id] % nro_t < nro_t - 1) {
     sm = solucion[posiciones[sig->id] / nro_t][posiciones[sig->id] % nro_t + 1];
   } else {
     sm = NULL;
   }
   sj = sig->sj;
   if(sm != NULL && r_sol[sm->id] + sm->costo + t_sol[sm->id] == costo_sol
      && r_sol[sm->id] - sig->costo == r_sol[sig->id]){
     //el sucesor en la maquina forma parte del camino critico
     push(sm->id, &camino);
     sig = sm;
   } else if(sj != NULL){
     //si el sucesor en la maquina no esta en el camino critico
     //entonces el sucesor en trabajo si lo esta
     push(sj->id, &camino);
     sig = sj;
   } else {
     break;
   }
 }
  
  //Copiar el resultado a un arreglo
  tama = tam(&camino);
  *nodos = (int *) calloc(tama, sizeof(int));

  for(i=0; i<tama; i++){
    (*nodos)[i] = desencolar(&camino);
  }
  return tama;
}

int calcular_r (operacion ***solucion, int *posiciones, int operaciones_est[], operacion *op) {
  int est, eft_pj = -1, eft_pm = -1;
  operacion *pm;
  if (!operaciones_est[op->id]) {
    if (posiciones[op->id] % nro_t > 0) {
      pm = solucion[posiciones[op->id] / nro_t][posiciones[op->id] % nro_t - 1];
      eft_pm = calcular_r(solucion,posiciones,operaciones_est,pm) + pm->costo;
    }
    if (op->pj) {
      eft_pj = calcular_r(solucion,posiciones,operaciones_est,op->pj) + op->pj->costo;
    }

    est = operaciones_est[op->id] = MAX(eft_pj, eft_pm);

    if(est == -1){
      est = operaciones_est[op->id] = 0;
    }
  } else {
    est = operaciones_est[op->id];
  }
  return est;
}

int calcular_t(operacion ***solucion, int *posiciones, int colas[], operacion *op ){
  int est, est_sm = -1, est_sj = -1;
  operacion *sm;
  if(!colas[op->id]){
    if(posiciones[op->id] % nro_t < nro_t - 1){
	  sm = solucion[posiciones[op->id] / nro_t][posiciones[op->id] % nro_t + 1];
      est_sm = calcular_t(solucion,posiciones,colas, sm) + sm->costo;
    }
    if(op->sj){
      est_sj = calcular_t(solucion,posiciones,colas, op->sj) + op->sj->costo;
    }

    est = colas[op->id] = MAX(est_sm, est_sj);

    if(est == -1){
      est = colas[op->id] = 0;
    }
  } else {
    est = colas[op->id];
  }
  return est;
}

int costo_solucion (operacion ***solucion, int *posiciones, int *operaciones_est, int *colas) {
  int i, est, max;

  for (i=0; i<nro_op; i++) {
    operaciones_est[i] = 0;
    colas[i] = 0;
  }
  est = calcular_r(solucion,posiciones,operaciones_est,solucion[0][nro_t-1]);
  max = solucion[0][nro_t-1]->id;
  for (i=1; i<nro_m; i++) {
    est = calcular_r(solucion,posiciones,operaciones_est,solucion[i][nro_t-1]) +  solucion[i][nro_t-1]->costo;
    if (est > operaciones_est[max] + operaciones[max].costo) {
      max = solucion[i][nro_t-1]->id;
    }
  }	

  for(i=0; i<nro_m; i++){
    calcular_t(solucion,posiciones,colas, solucion[i][0]);
  }

  return operaciones_est[max] + operaciones[max].costo;
}

/* Ejecuta el movimiento de las operaciones que se encuentran en el orden
 * representado por el arreglo actual para que queden en el orden representado
 * por el arreglo movimiento
 * Parametros:
 *		actual: arreglo que representa el orden actual de las operaciones
 *				involucradas en el movimiento
 *		movimiento: arreglo que representa el orden de las operaciones
 *					despues de ejecutar el movimiento
 *		tam_movimiento: cantidad de operaciones involucradas en el movimiento
 *		inicial: arreglo de operaciones iniciales de cada maquina
 *		final: arreglo de operaciones finales de cada maquina
 */
void hacer_movimiento (operacion ***solucion, int *posiciones, operacion *actual[], operacion *movimiento[], int tam_movimiento) {
  int i, j, pos;
  
  pos = posiciones[actual[0]->id];
  
  for (i=0; i<tam_movimiento; i++) {
    solucion[pos / nro_t][pos % nro_t] = movimiento[i];
    posiciones[movimiento[i]->id] = pos++;
  }
}

/* Calcula el movimiento que se debe realizar para obtener el mejor vecino
 * segun la vecindad N1
 * Parametros:
 *		actual: arreglo que representa el orden actual de las operaciones
 *				involucradas en el mejor movimiento
 *		mejor: arreglo que representa el orden de las operaciones
 *			   despues de ejecutar el mejor movimiento
 *		primeros: arreglo de operaciones iniciales de cada maquina
 *		ultimos: arreglo de operaciones finales de cada maquina
 *		costo_sol: entero que representa el costo de la solucion
 *		r_sol: arreglo de tiempos de comienzo mas temprano de cada operacion
 *		t_sol: arreglo de tiempos desde que termina cada operacion hasta que
 *			   finalizan todos los trabajos
 * Valor de retorno:
 *		-1 en caso de no encontrar algun vecino que no esta prohibido
 *		en otro caso, cantidad de operaciones involucradas en el mejor movimiento
 */
int mejor_movimiento_n1 (operacion ***solucion, int *posiciones, operacion *actual[], operacion *mejor[], operacion ** primeros, operacion ** ultimos, int costo_sol, int r_sol[], int t_sol[]) {
  int i, *cam_crit, tam_cam_crit, u, v;
  int mejor_cota, mejor_cota_aux, tam_movimiento, tam_movimiento_aux;
  operacion *actual_aux[3], *mejor_aux[3];

  int found = 0;
  tam_cam_crit = camino_critico(&cam_crit, solucion, posiciones, costo_sol, r_sol, t_sol);
	
  //busco un primer movimiento
    for (i=0; i<tam_cam_crit-1; i++) {
        if (operaciones[cam_crit[i]].maquina == operaciones[cam_crit[i+1]].maquina) {
            actual[0] = operaciones + cam_crit[i];
			actual[1] = operaciones + cam_crit[i+1];
			mejor[0] = operaciones + cam_crit[i+1];
			mejor[1] = operaciones + cam_crit[i];
			hacer_movimiento(solucion,posiciones,actual,mejor,2);
			mejor_cota = costo_solucion(solucion,posiciones, r_sol, t_sol);
			hacer_movimiento(solucion,posiciones,mejor,actual,2);
			u = cam_crit[i];
			v = cam_crit[i+1];
			i++;
			found = 1;
			break;
        }
    }
    //busco el mejor movimiento
    for (; i<tam_cam_crit-1; i++) {
        if (operaciones[cam_crit[i]].maquina == operaciones[cam_crit[i+1]].maquina) {
            actual_aux[0] = operaciones + cam_crit[i];
			actual_aux[1] = operaciones + cam_crit[i+1];
			mejor_aux[0] = operaciones + cam_crit[i+1];
			mejor_aux[1] = operaciones + cam_crit[i];
			hacer_movimiento(solucion,posiciones,actual_aux,mejor_aux,2);
			mejor_cota_aux = costo_solucion(solucion, posiciones, r_sol, t_sol);
			hacer_movimiento(solucion,posiciones,mejor_aux,actual_aux,2);
            if (mejor_cota_aux < mejor_cota) {
                mejor_cota = mejor_cota_aux;
                memcpy(actual, actual_aux, 2*sizeof(operacion *));
                memcpy(mejor, mejor_aux, 2*sizeof(operacion *));
                u = cam_crit[i];
                v = cam_crit[i+1];
            }
        }
    }
  if(!found) return -1;
 
  free(cam_crit);

  return 2;
}

int local_search (operacion ***solucion) {
  int i, j, k, posiciones[nro_op], r_sol[nro_op], t_sol[nro_op], *cam_crit, tam_cam_crit;
  int costo_actual, costo_mejor, tam_movimiento;
  operacion* primeros[nro_m], *ultimos[nro_m], *actual[3], *movimiento[3], *mejor_solucion[nro_m][nro_t];

  for (i=0; i<nro_m; i++) {
	for (j=0; j<nro_t; j++) {
      posiciones[solucion[i][j]->id] = i*nro_t + j;
    }
  }

  costo_mejor = costo_actual = costo_solucion(solucion, posiciones, r_sol, t_sol);

  while (1) {
    for (i=0; i<nro_m; i++) {
      primeros[i] = solucion[i][0];
      ultimos[i] = solucion[i][nro_t-1];
    }
    tam_movimiento = mejor_movimiento_n1(solucion, posiciones, actual, movimiento, primeros, ultimos, costo_actual, r_sol,t_sol);

    if(tam_movimiento == -1){ //no hay mas vecinos
		printf("HOOLAAA\n");
      break;
    }

    hacer_movimiento(solucion,posiciones,actual,movimiento,tam_movimiento);

    costo_actual = costo_solucion(solucion, posiciones, r_sol, t_sol);

    if (costo_actual < costo_mejor) {
      costo_mejor = costo_actual;
      
      //Se guarda la mejor solucion
      for(j=0; j<nro_m; j++) {
        for (k=0; k<nro_t; k++) {
          mejor_solucion[j][k] = solucion[j][k];
        }
      }
    } else {//criterio de parada (no se encontro un mejor vecino)
      break;
    }
  }

  for(j=0; j<nro_m; j++) {
    for (k=0; k<nro_t; k++) {
      solucion[j][k] = mejor_solucion[j][k];
    }
  }
  return costo_mejor;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

int operacion_a_asignar (int *arr, int tam, int *eft_maq, int *eft_job, double alfa) {
    int i, menor, mayor, mks_menor, mks_mayor, mks_aux, r;
    
    //se buscan las operaciones que al planificarlas aumentan mas y menos el makespan
    menor = mayor = arr[0];
    mks_menor = MAX(eft_maq[operaciones[menor].maquina],eft_job[menor / nro_m]) + operaciones[menor].costo;
    mks_mayor = MAX(eft_maq[operaciones[mayor].maquina],eft_job[mayor / nro_m]) + operaciones[mayor].costo;
    for (i=1; i<tam; i++) {
        mks_aux = MAX(eft_maq[operaciones[arr[i]].maquina],eft_job[arr[i] / nro_m]) + operaciones[arr[i]].costo;
        if (mks_aux < mks_menor) {
            menor = arr[i];
            mks_menor = mks_aux;
        }
        if (mks_aux > mks_mayor) {
            mayor = arr[i];
            mks_mayor = mks_aux;
        }
    }
    
    while (1) {
        r = rand() % tam;
        mks_aux = MAX(eft_maq[operaciones[arr[r]].maquina],eft_job[arr[r] / nro_m]) + operaciones[arr[r]].costo;
        if (mks_aux <= mks_menor + alfa * (mks_mayor - mks_menor)) {
            break;
        }
    }
    return arr[r];
}

/* Elimina un elemento de un arreglo de enteros
 * Parametros:
 *		arr: el arreglo donde se va a eliminar el elemento
 *		tam: longitud del arreglo arr
 *		elem: elemento del arreglo que se quiere eliminar
 */
void quitar(int* arr, int tam, int elem){
  int i;
  for(i = 0; i<tam; i++){
    if(arr[i] == elem){
      arr[i] = arr[tam-1];
      return;
    }
  }
}

int construir_solucion () {
  int i, t, tam_L, maq_t, costo_solucion;
  int L[nro_t], eft_maq[nro_m], eft_job[nro_t];

  for(i=0; i<nro_t; i++){
    L[i] = nro_m*i;
    eft_job[i] = 0;
  }
  tam_L = nro_t;
  
  for(i=0; i<nro_m; i++){
    inicio[i] = 0;
    fin[i] = 0;
    eft_maq[i] = 0;
  }
   
  while(tam_L > 0){
    t = operacion_a_asignar(L, tam_L, eft_maq, eft_job, alfa);
    maq_t = operaciones[t].maquina;
    
    if (eft_maq[maq_t] > eft_job[t / nro_m]) {
        eft_maq[maq_t] += operaciones[t].costo;
        eft_job[t / nro_m] = eft_maq[maq_t];
    } else {
        eft_job[t / nro_m] += operaciones[t].costo;
        eft_maq[maq_t] = eft_job[t / nro_m];
    }

    if (inicio[maq_t] != 0) {
      operaciones[t].pm = fin[maq_t];
      fin[maq_t]->sm = operaciones + t;
    } else {
      inicio[maq_t] = operaciones + t;
      operaciones[t].pm = 0;
    }

    fin[maq_t] = operaciones + t;

    quitar(L, tam_L, t);
    tam_L--;
    if((t+1) % nro_m != 0){
      L[tam_L] = t+1;
      tam_L++;
    }
  }
  
  //costo de la solucion
  costo_solucion = eft_maq[0];
  for (i=1; i<nro_m; i++) {
    if (eft_maq[i] > costo_solucion) costo_solucion = eft_maq[i];
  }
  return costo_solucion;
}

void grasp () {
    int i, j, k, costo_solucion;
    operacion ***solucion;
    
    solucion = (operacion ***) calloc(nro_m,sizeof(operacion **));

    for (i=0; i<nro_m; i++) {
      solucion[i] = (operacion **) calloc(nro_t,sizeof(operacion *));
    }

    for (i=0; i<nro_iteraciones; i++) {
        costo_solucion = construir_solucion();
        
        //guardo solucion en la matriz solucion
        for(j=0; j<nro_m; j++) {
            operacion *op = inicio[j];
            for (k=0; k<nro_t; k++) {
                solucion[j][k] = op;
                op = op->sm;
            }
        }
        
        //aplico local search
        costo_solucion = local_search(solucion);
        
        if (costo_solucion < costo_mejor || costo_mejor == 0) {
            costo_mejor = costo_solucion;
            //guardo mejor solucion
            for(j=0; j<nro_m; j++) {
                for (k=0; k<nro_t; k++) {
                    mejor_solucion[j][k] = solucion[j][k];
                }
            }
        }
    }
}

void seed () {
    struct timeval t;
    gettimeofday(&t,NULL);
    srand(t.tv_sec * t.tv_usec);
}

int main (int argc, char **argv) {
  int error, option;
  extern char *optarg;
  extern int optopt;
  char *archivo_instancia = NULL;
  clock_t start, end;
  seed();
  start = clock();
  
  //parametros por defecto
  nro_iteraciones = 1000;
  alfa = 0.5;

  while ((option = getopt(argc,argv,":n:a:f:")) != -1) {
    switch (option) {
    case 'n':
      nro_iteraciones = atoi(optarg);
      break;
    case 'a':
      alfa = atof(optarg);
      break;
    case 'f':
      archivo_instancia = optarg;
      break;
    case ':':
      printf("ERROR: a la opcion -%c le falta su argumento\n",optopt);
      exit(1);
    case '?':
      printf("ERROR: parametro desconocido %c\n",optopt);
      exit(1);
      
    }
  }
  
  if (!archivo_instancia) {
    printf("Debe especificar un archivo de caso de prueba.\nUse el flag -f <archivo>\n");
    exit(1);
  }
  
  if(nro_iteraciones <= 0){
    printf("El numero de iteraciones debe ser mayor que 0.\n");
    exit(1);
  }
  
  if(alfa < 0 || alfa > 1){
    printf("El parametro alfa debe ser mayor o igual a 0 y menor o igual a 1.\n");
    exit(1);
  }
  
  if (error = leer_instancia(archivo_instancia)) {
    if (error == -1) printf("ERROR: la memoria disponible no es suficiente\n");
  	exit(1);
  }

  grasp();
  
  end = clock();
  //  printf("Mejor costo: %d\n",costo_mejor);
  printf("%d ", costo_mejor);
  //  imprimir_solucion();
  printf("%5.2f seg.\n",((double) (end - start)) / CLOCKS_PER_SEC );
  return 0;
}
